package com.xiaoyu.a;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * Comments：
 * Author：yuxin
 * Create Date：2017-06-22
 * Modified By：
 * Modified Date：
 * Why & What is modified：
 * Version：v1.0
 */
public class Astar {
    public final static int BAR = 1; // 障碍值
    public final static int PATH = 2; // 路径
    public final static int DIRECT_VALUE = 10; // 横竖移动代价
    public final static int OBLIQUE_VALUE = 14; // 斜移动代价

    Queue<Node> openList = new PriorityQueue<Node>(); // 优先队列(升序)
    List<Node> closeList = new ArrayList<Node>();

    /**
     * 开始算法
     */
    public void start(MapInfo mapInfo)
    {
        if(mapInfo==null) return;
        // clean
        openList.clear();
        closeList.clear();
        // 开始搜索
        openList.add(mapInfo.start);
        moveNodes(mapInfo);//开始移动
    }

    /**
     * 移动当前结点
     */
    private void moveNodes(MapInfo mapInfo)
    {
        while (!openList.isEmpty())//如果为空，就是没有路径
        {
            if (isCoordInClose(mapInfo.end.coord))//判断终节点是否在colse表中，如果是，就停止.
            {
                drawPath(mapInfo.maps, mapInfo.end);
                return;
            }
            Node current = openList.poll();
            closeList.add(current);
            addNeighborNodeInOpen(mapInfo,current);//添加所有邻结点到open表
        }
    }

    /**
     * 在二维数组中绘制路径
     */
    private void drawPath(int[][] maps, Node end)
    {
        if(end==null||maps==null) return;
        System.out.println("总代价：" + end.G);
        while (end != null)
        {
            Coord c = end.coord;
            maps[c.y][c.x] = PATH;//先把最后的终点标为2，通过父节点一点点往前移都标上2
            end = end.parent;
        }
    }

    /**
     * 添加所有邻结点到open表
     */
    private void addNeighborNodeInOpen(MapInfo mapInfo,Node current)
    {
        int x = current.coord.x;
        int y = current.coord.y;
        // 左
        addNeighborNodeInOpen(mapInfo,current, x - 1, y, DIRECT_VALUE);
        // 上
        addNeighborNodeInOpen(mapInfo,current, x, y - 1, DIRECT_VALUE);
        // 右
        addNeighborNodeInOpen(mapInfo,current, x + 1, y, DIRECT_VALUE);
        // 下
        addNeighborNodeInOpen(mapInfo,current, x, y + 1, DIRECT_VALUE);

            // 左上
            addNeighborNodeInOpen(mapInfo, current, x - 1, y - 1, OBLIQUE_VALUE);


            // 右上
            addNeighborNodeInOpen(mapInfo, current, x + 1, y - 1, OBLIQUE_VALUE);


            // 右下
            addNeighborNodeInOpen(mapInfo, current, x + 1, y + 1, OBLIQUE_VALUE);


            // 左下
            addNeighborNodeInOpen(mapInfo, current, x - 1, y + 1, OBLIQUE_VALUE);

    }

    /**
     * 添加一个邻结点到open表
     */
    private void addNeighborNodeInOpen(MapInfo mapInfo,Node current, int x, int y, int value)
    {

        if (canAddNodeToOpen(mapInfo,x, y,value))//判断结点能否放入Open列表
        {
            Node end=mapInfo.end;
            Coord coord = new Coord(x, y);
            int G = current.G + value; // 计算邻结点的G值
            Node child = findNodeInOpen(coord);//从Open列表中查找结点(如果有已经在openlist里面的就再算他的G值,就是下面的else if)
            if (child == null)
            {
                int H=calcH(end.coord,coord); // 计算H值
                if(isEndNode(end.coord,coord))//判断结点是否是最终结点
                {
                    //child=new Node(end.coord,current,G,H);           //把end节点覆盖了,end节点的父结点,G,H都没了
                    child=end;
                    child.parent=current;
                    child.G=G;
                    child.H=H;
                }
                else
                {
                    child = new Node(coord, current, G, H);
                }
                openList.add(child);
            }
            else if (child.G > G)//计算其实没用的点的G的最小值
            {
                child.G = G;
                child.parent = current;
                openList.add(child);
            }
        }
    }

    /**
     * 从Open列表中查找结点
     */
    private Node findNodeInOpen(Coord coord)
    {
        if (coord == null || openList.isEmpty()) return null;
        for (Node node : openList)
        {
            if (node.coord.equals(coord))
            {
                return node;
            }
        }
        return null;
    }


    /**
     * 计算H的估值：“曼哈顿”法，坐标分别取差值相加
     */
    private int calcH(Coord end,Coord coord)
    {
        return Math.abs(end.x - coord.x)*10
                + Math.abs(end.y - coord.y)*10;
    }

    /**
     * 判断结点是否是最终结点
     */
    private boolean isEndNode(Coord end,Coord coord)
    {
        return coord != null && end.equals(coord);
    }

    /**
     * 判断结点能否放入Open列表
     */
    private boolean canAddNodeToOpen(MapInfo mapInfo,int x, int y,int value)
    {
        // 是否在地图中
        if (x < 0 || x >= mapInfo.width || y < 0 || y >= mapInfo.hight) return false;
        // 判断是否是不可通过的结点
        if (mapInfo.maps[y][x] == BAR) return false;
        //下面的4个判断其实是有问题的
        if(y-1>0) {//右下,左下
            if (value == OBLIQUE_VALUE && mapInfo.maps[y - 1][x] == BAR) return false;
        }
        if(y+1<mapInfo.hight) {//左上，右上
            if (value == OBLIQUE_VALUE && mapInfo.maps[y + 1][x] == BAR) return false;
        }
        if(x-1>0) {//右上，右下
            if (value == OBLIQUE_VALUE && mapInfo.maps[y ][x-1] == BAR) return false;
        }
        if(x+1<mapInfo.width) {//左上,左下
            if (value == OBLIQUE_VALUE && mapInfo.maps[y ][x+1] == BAR) return false;
        }
        // 判断结点是否存在close表
        if (isCoordInClose(x, y)) return false;

        return true;
    }

    /**
     * 判断坐标是否在close表中
     */
    private boolean isCoordInClose(Coord coord)
    {
        return coord!=null&&isCoordInClose(coord.x, coord.y);
    }

    /**
     * 判断坐标是否在close表中
     */
    private boolean isCoordInClose(int x, int y)
    {
        if (closeList.isEmpty()) return false;
        for (Node node : closeList)
        {
            if (node.coord.x == x && node.coord.y == y)
            {
                return true;
            }
        }
        return false;
    }
}
